{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[0.5, 0.2, 0.3],\n",
       "        [0.3, 0.5, 0.2],\n",
       "        [0.2, 0.3, 0.5]]), array([[0.5, 0.5],\n",
       "        [0.4, 0.6],\n",
       "        [0.7, 0.3]]), array([0.2, 0.4, 0.4]), [0, 1, 0])"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "#A是状态转换概率矩阵,标识不同状态之间相互转换的概率\n",
    "A = np.array([[0.5, 0.2, 0.3], [0.3, 0.5, 0.2], [0.2, 0.3, 0.5]])\n",
    "\n",
    "#B是输出概率矩阵,标识在不同状态下各个输出的概率\n",
    "B = np.array([[0.5, 0.5], [0.4, 0.6], [0.7, 0.3]])\n",
    "\n",
    "#pi是第一次会进去某个状态的概率\n",
    "pi = np.array([0.2, 0.4, 0.4])\n",
    "\n",
    "#out是输出链,这里标识的是红球,白球,红球\n",
    "out = [0, 1, 0]\n",
    "\n",
    "#xi是(序列长度,状态数量)形状的矩阵,每一行是一个时刻,每一列是由该状态输出的概率\n",
    "#以xi[0,0]为例,指的是时刻0,由状态0输出结果的概率\n",
    "xi = np.zeros((3, 3))\n",
    "\n",
    "#phi里记录的是最有可能的路径\n",
    "#以phi[1,0]为例,指的是哪一个时刻0的状态最有可能转移到时刻1的状态0\n",
    "phi = np.zeros((3, 3))\n",
    "\n",
    "A, B, pi, out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.1 , 0.16, 0.28],\n",
       "       [0.  , 0.  , 0.  ],\n",
       "       [0.  , 0.  , 0.  ]])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#这里处理t0的xi\n",
    "\n",
    "#在时刻0,由状态0输出out[0]的概率,当然就是pi[0] * B[0]out[0]\n",
    "xi[0, 0] = pi[0] * B[0, out[0]]\n",
    "\n",
    "#在时刻0,由状态1输出out[0]的概率,当然就是pi[1] * B[1]out[0]\n",
    "xi[0, 1] = pi[1] * B[1, out[0]]\n",
    "\n",
    "#在时刻0,由状态2输出out[0]的概率,当然就是pi[2] * B[2]out[0]\n",
    "xi[0, 2] = pi[2] * B[2, out[0]]\n",
    "\n",
    "xi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 0.055999999999999994)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#求下一个时刻转移到状态a,概率最高的是当前时刻t的哪一个状态\n",
    "def max_next_time_to_a(t, a):\n",
    "    prob = np.zeros(3)\n",
    "\n",
    "    #当前时刻的状态是0的概率就是xi[t-1,0],再乘以转移到状态a的概率,就是A[0,a]\n",
    "    prob[0] = xi[t, 0] * A[0, a]\n",
    "\n",
    "    #当前时刻的状态是1的概率就是xi[t-1,1],再乘以转移到状态a的概率,就是A[1,a]\n",
    "    prob[1] = xi[t, 1] * A[1, a]\n",
    "\n",
    "    #当前时刻的状态是2的概率就是xi[t-1,2],再乘以转移到状态a的概率,就是A[2,a]\n",
    "    prob[2] = xi[t, 2] * A[2, a]\n",
    "\n",
    "    #只需要概率最高的\n",
    "    return prob.argmax(), prob.max()\n",
    "\n",
    "\n",
    "#在时刻0,转移到时刻1的状态0的概率\n",
    "#最高的是从时刻0的状态2以0.0559的概率转移到时刻1的状态0\n",
    "max_next_time_to_a(t=0, a=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[0.1   , 0.16  , 0.28  ],\n",
       "        [0.028 , 0.0504, 0.042 ],\n",
       "        [0.    , 0.    , 0.    ]]), array([[0., 0., 0.],\n",
       "        [2., 2., 2.],\n",
       "        [0., 0., 0.]]))"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#这里处理t1的xi和phi\n",
    "\n",
    "#在时刻0,转移到时刻1的状态0的概率\n",
    "a, prob = max_next_time_to_a(t=0, a=0)\n",
    "\n",
    "#在时刻1,由状态0输出out[1]的概率,就是时刻0转移到状态0的概率 * B[0]out[1]\n",
    "xi[1, 0] = B[0][out[1]] * prob\n",
    "\n",
    "#哪一个时刻0的状态最有可能转移到时刻1的状态0\n",
    "phi[1, 0] = a\n",
    "\n",
    "a, prob = max_next_time_to_a(t=0, a=1)\n",
    "xi[1, 1] = B[1][out[1]] * prob\n",
    "phi[1, 1] = a\n",
    "\n",
    "a, prob = max_next_time_to_a(t=0, a=2)\n",
    "xi[1, 2] = B[2][out[1]] * prob\n",
    "phi[1, 2] = a\n",
    "\n",
    "xi, phi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[0.1    , 0.16   , 0.28   ],\n",
       "        [0.028  , 0.0504 , 0.042  ],\n",
       "        [0.00756, 0.01008, 0.0147 ]]), array([[0., 0., 0.],\n",
       "        [2., 2., 2.],\n",
       "        [1., 1., 2.]]))"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#这里处理t2的xi和phi\n",
    "\n",
    "a, prob = max_next_time_to_a(t=1, a=0)\n",
    "xi[2, 0] = B[0][out[2]] * prob\n",
    "phi[2, 0] = a\n",
    "\n",
    "a, prob = max_next_time_to_a(t=1, a=1)\n",
    "xi[2, 1] = B[1][out[2]] * prob\n",
    "phi[2, 1] = a\n",
    "\n",
    "a, prob = max_next_time_to_a(t=1, a=2)\n",
    "xi[2, 2] = B[2][out[2]] * prob\n",
    "phi[2, 2] = a\n",
    "\n",
    "xi, phi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([2, 2, 2]), 0.014699999999999998)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#尝试回溯状态链\n",
    "viterbi = np.empty(3, dtype=int)\n",
    "\n",
    "#时刻2,输出结果概率最大的那个状态\n",
    "viterbi[2] = xi[2].argmax()\n",
    "\n",
    "#哪一个时刻1的状态最有可能转移到时刻2输出结果概率最大的那个状态\n",
    "viterbi[1] = phi[2, viterbi[2]]\n",
    "\n",
    "#哪一个时刻0的状态最有可能转移到时刻1输出结果概率最大的那个状态\n",
    "viterbi[0] = phi[1, viterbi[1]]\n",
    "\n",
    "#这个状态链的估计有多大信心\n",
    "viterbi_score = xi[2].max()\n",
    "\n",
    "viterbi, viterbi_score"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
